package hdgeom.procedures;

import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.Vector;

import processing.core.*;
import simpleGeom.HasPos2D;
import simpleGeom.Vec2D;

public class ConvexHull {

	public Vector<HasPos2D> pts;
	public Vector<HasPos2D>hull;
	
	public ConvexHull(Vector<? extends HasPos2D> p){
		
		hull=computeHull(p);
	}
	
	public Vector<HasPos2D> getConvexHull(){
		return hull;
	}
	
	private Vector<HasPos2D> computeHull(Vector<? extends HasPos2D> p) {
		pts = new Vector<HasPos2D>(p);
		// pts.addAll(p);
		if (pts.size() < 3)
			return pts;
		return grahamScan();

	}

	/*public Vector<PVector> computeHullPolygon(Vector<PVector> p) {
		pts = new Vector<PVector>();
		pts.addAll(p);
		if (pts.size() < 3)
			return pts;
		return computeHull(p);

	}*/

	private Vector<HasPos2D> computeHullOfSorted2(Vector<HasPos2D> pts) {
		Vector<HasPos2D> hull = new Vector<HasPos2D>();
		HasPos2D p0 = pts.firstElement();
		hull.add(p0);

		HasPos2D p1 = pts.get(1);
		hull.add(p1);

		HasPos2D p2 = pts.get(2);
		hull.add(p2);

		for (int i = 3; i < pts.size(); i++) {
			p0 = p1;
			p1 = p2;
			p2 = pts.get(i);
			hull.add(p2);

			while (Vec2D.relativeCCW(p0, p2, p1) == Vec2D.CWRIGHT) {
				hull.remove(hull.size() - 2);
				p1 = p0;
				p0 = hull.get(hull.size() - 3);
			}
		}
		return hull;
	}
	
	private Vector<HasPos2D> computeHullOfSorted(Vector<HasPos2D> pts) {
	//	Vector<PVector> hull = new Vector<PVector>();
		Stack<HasPos2D>hull=new Stack<HasPos2D>();
		HasPos2D p0 = pts.firstElement();
		hull.add(p0);
		HasPos2D p1 = pts.get(1);
		hull.add(p1);
		int n=pts.size();
		int i=2;
		while(i<n){
			p0 = hull.peek();
			p1 = hull.get(hull.size()-2);
			HasPos2D s = pts.get(i);
			//int dir=PVecMath2D.relativeCCW(p0,p1,s);
			if (Vec2D.relativeCCW(p0,p1,s) != Vec2D.CWRIGHT) {
				hull.add(s);
				i++;
			}
			else{
				hull.pop();
			}
		}
		return hull;
	}


	private Vector<HasPos2D> grahamScan() {
		HasPos2D pl = lowestPoint();
		Vec2D sub = new Vec2D(pl.getX(), pl.getY());
		makeRelTo(sub);
		Collections.sort(pts, new Point2DComparator());
		sub.setPosition(sub.x * -1f, sub.y * -1f);
		makeRelTo(sub);
		return computeHullOfSorted(pts);
	}

	private void makeRelTo(HasPos2D p0) {
		for (int i = 0; i < pts.size(); i++) {
			HasPos2D p = pts.get(i);
			Vec2D newP=Vec2D.sub(p, p0);
			p.setPosition(newP.getX(), newP.getY());
			
		}
	}

	private HasPos2D lowestPoint() {
		HasPos2D minP = pts.firstElement();
		for (int i = 1; i < pts.size(); i++) {
			HasPos2D p = pts.get(i);
			if (p.getY() < minP.getY() || (p.getY() == minP.getY() && p.getX() < minP.getX()))
				minP = p;
		}
		return minP;
	}

	class Point2DComparator implements Comparator<HasPos2D> {
		public int compare(HasPos2D p1, HasPos2D p2) {
			// TODO Auto-generated method stub
			
			double cArea = p1.getX() * p2.getY() - p2.getX() * p1.getY();
			if (p1.getX()==p2.getX()&&p1.getY()==p2.getY()){
				System.out.println("the same");
			}
			if (cArea < 0)
				return -1;
			if (cArea > 0)
				return 1;
			double d1 = Math.abs(p1.getX()) + Math.abs(p1.getY());
			double d2 = Math.abs(p2.getX()) + Math.abs(p2.getY());
			//System.out.println("sameAngle");
			
			if (d1< d2)
				return -1;
			else
				return 1;
		}
	}

} // end class GrahamScan

